| 题目名称 |
九九归一 |
LCA 的统计 |
四驱兄弟 |
| 目录 |
mulone |
lcastat |
letsandgo |
| 可执行文件名 |
mulone |
lcastat |
letsandgo |
| 每个测试点时限 |
1s |
1s |
1s |
| 内存限制 |
128M |
128M |
128M |
| 测试点数目 |
10 |
10 |
10 |
| 每个测试点分值 |
10 |
10 |
10 |
| 是否有部分分 |
无 |
无 |
无 |
| 题目类型 |
传统 |
传统 |
传统 |
九九归一
【问题描述】
萌蛋在练习模𝑛意义下的乘法时发现，总有一些数，在自乘若干次以后，会 变成 1。例如𝑛 = 7，那么5 × 5 𝑚𝑜𝑑 7 = 4,4 × 5 𝑚𝑜𝑑 7 = 6,6 × 5 𝑚𝑜𝑑 7 = 2,2 × 5 𝑚𝑜𝑑 7 = 3,3 × 5 𝑚𝑜𝑑 7 = 1。如果继续乘下去，就会陷入循环当中。 萌蛋还发现，这个循环的长度经常会是φ(𝑛)，即小于𝑛且与𝑛互质的正整数 的个数。例如，φ(7) = 6，而上述循环的长度也是 6，因为 5,4,6,2,3,1 共有 6 个 数。 再如𝑛 = 6，那么5 × 5 𝑚𝑜𝑑 6 = 1。这个循环的长度很短，只有 2，而恰好 φ(6) = 2。 然而，对于某些情况，虽然循环的长度可以是φ(𝑛)，但存在比φ(𝑛)更小的长 度：例如𝑛 = 7，而2 × 2 𝑚𝑜𝑑 7 = 4,4 × 2 𝑚𝑜𝑑 7 = 1，循环的长度只有 3。当然， 6 也可以是一个循环的长度。 假设已知了𝑛，我们称数𝑎神奇的，当且仅当关于数𝑎的循环长度可以是φ(𝑛)， 而且不存在比φ(𝑛)更小长度的循环。例如对于𝑛 = 7，5 是神奇的，而 2 不是神 奇的。 现在给出𝑛和𝑞次询问，每次询问给出𝑎，问𝑎是否是神奇的。
【输入文件】
第一行两个整数𝑛 𝑞。 第二行有𝑞个整数，每个表示一个𝑎。
【输出文件】
输出𝑞个字符，1 表示这个数是神奇的，0 表示这个数不是神奇的。
【输入样例】
7 3 5 2 0
【输出样例】
100
【数据规模和约定】
对于 30%的数据，𝑛 ≤ 1,000。
对于 60%的数据，𝑛 ≤ 100,000。
对于 80%的数据，𝑛 ≤ 1,000,000。
对于 100%的数据，𝑛 ≤ 10,000,000,𝑞 ≤ 100,000,0 ≤ 𝑎 < 𝑛。
Solution
和昨天的哪一题有点像，还是比较裸的，题目的要求已经说的很清楚了，要求
且满足任意一个φ(𝑛)的因子不满足上述式子即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #define LL long long using namespace std; int n,q,phin; bool flag[10000010]; int phi[10000010],prime[10000010],Div[1000010]; void Pre_Phi() { for(int i=2;i<=10000010;i++) { if(!flag[i])prime[++prime[0]]=i,phi[i]=i-1; for(int j=1;j<=prime[0]&&i*prime[j]<=10000000;j++) { flag[i*prime[j]]=true; phi[i*prime[j]]=phi[i]*(prime[j]-1); if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } } } } void Pre_Check() { for(int i=2;i<=sqrt(phin);i++){ if(phin%i==0) Div[++Div[0]]=i,Div[++Div[0]]=phin/i; } } int quickpow(int x,int y) { int rtn=1; while(y) { if(y&1)rtn=((LL)rtn*x)%n; x=((LL)x*x)%n; y>>=1; } return rtn%n; } int main() { freopen("mulone.in","r",stdin); freopen("mulone.out","w",stdout); Pre_Phi(); scanf("%d%d",&n,&q); phin=phi[n]; Pre_Check(); while(q--) { int a,f=0; scanf("%d",&a); for(int i=1;i<=Div[0];i++) { int d=Div[i]; int c=quickpow(a,d); if(c==1){ printf("0"); f=1; break; } } if(f==0&&quickpow(a,phin)==1)printf("1"),f=1; if(f==0)printf("0"); } return 0; } 7 3 5 2 0 */
|
LCA 的统计
【问题描述】
萌蛋有一棵𝑛个节点的有根树，其根节点为 1。除此之外，节点𝑖的父节点 为𝑝𝑖。每个点上都有一个权值，节点𝑖的权值是𝑤𝑖。 萌蛋知道你一定知道什么叫做祖先（从根到某个点的路径上的每个点都是 这个点的祖先，包括它本身），也一定知道什么叫做最近公共祖先（两个点的最 近公共祖先是某个点，这个点同时是两个点的祖先，且离根最远）。 现在给出这棵树，你需要求出：
其中𝐿𝐶𝐴(𝑖,𝑗)表示点𝑖与点𝑗的最近公共祖先。 由于答案可能很大，你只需要输出它对 1,000,000,007 取模的结果。
【输入文件】
第一行为两个整数𝑛 𝑤1。 第二行到第𝑛行，第𝑖行有两个整数𝑝𝑖 𝑤𝑖。
【输出文件】
输出只有一行，为一个整数，表示所求答案对 1,000,000,007 取模的结果。
【输入样例】
2 2
1 1
【输出样例】
17
【样例解释】
1 × 1 × 1 + 1 × 2 × 2 + 2 × 1 × 2 + 2 × 2 × 2 = 17。
【数据规模和约定】
对于30%的数据，𝑛 ≤ 100,𝑤𝑖 ≤ 10。
对于 60%的数据，𝑛 ≤ 1,000,𝑤𝑖 ≤ 1,000。
对于 100%的数据，1 ≤ 𝑛 ≤ 100,000,0 ≤ 𝑤𝑖 ≤ 1,000,000,000,1 ≤ 𝑝𝑖 < 𝑖。
Solution
树上dp，因为这道题今天ak失败,是菜啊，考虑一个点作为LCA的情况，根据题目给出的式子有三种情况：
1.i,j,k均为一个点，那么直接^3;
2.i,j重合,他的所有儿子的都对答案有贡献，别忘记乘二;
3.最麻烦的是i,j分别在两个不同的子树中，考虑一个二叉树，编号从1~7,当1是LCA时，你可以手动枚举一下，然后合并什么的，就可得到一个式子:ans+=w1(w2+w4+w5)(w3+w6+w7)。那么就应该做出一个子树和，便于统计。对于不是二叉树的，依旧可以通过他的子树统计，统计方法枚举一个儿子，他具有和其他儿子配对的可能性，然后用是s[k]-s[kk]就得到了所有其他儿子的配对数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #define mod 1000000007 #define LL long long using namespace std; int cnt,n,w1,p[100010]; LL w[100010],s[100010],ans=0; struct node{ int a,b,nt; }e[1000010]; void add(int x,int y){ cnt++; e[cnt].a=x,e[cnt].b=y,e[cnt].nt=p[x],p[x]=cnt; } void dfs(int k) { ans=(ans+((w[k]*w[k])%mod)*w[k]%mod)%mod; s[k]=w[k]; for(int i=p[k];i;i=e[i].nt) { int kk=e[i].b; dfs(kk); ans=(ans+((w[k]*w[k])%mod*s[kk])%mod*2%mod)%mod; s[k]=(s[k]+s[kk])%mod; } for(int i=p[k];i;i=e[i].nt) { int kk=e[i].b; ans=(ans+((w[k]*s[kk])%mod*(s[k]+mod-w[k]-s[kk])%mod)%mod)%mod; } return; } int main() { freopen("lcastat.in","r",stdin); freopen("lcastat.out","w",stdout); scanf("%d%d",&n,&w[1]); for(int i=2;i<=n;i++) { int fa; scanf("%d%d",&fa,&w[i]); add(fa,i); } dfs(1); printf("%lld\n",ans%mod); return 0; }
|
四驱兄弟
【问题描述】
如果你和萌蛋一样，也看过《四驱兄弟》，你或许会记得，有一局比赛十分 特别，只按照 5 个人中的第 4 名计算成绩。 现在我们将问题扩展一下：一共有𝑛个队员，只按照其中的第𝑘名计算成 绩。而赛车的规则也有所不同：一共有𝑚个赛车，每个赛车装配着 2 个 GP 晶 片的终端，且第𝑖个赛车预期到达终点的时间为𝑎𝑖。（注：不同赛车上的终端可 以对应着相同的 GP 晶片，但不会 2 个都相同；任何赛车上的 2 个终端对应的 GP 晶片都是不同的） 比赛开始时，𝑛个队员依次选择自己的赛车。对于每个队员，他可以选择开 启 GP 晶片功能或不开启。如果开启，那么 2 个终端对应的 GP 晶片就会建立连 接，且这个赛车的比赛用时就是预期时间𝑎𝑖；如果不开启，那么 GP 晶片不会 建立连接，但是这个赛车的比赛用时将会非常长（可以认为是无穷）。甚至，他 可以放弃比赛，这样他不会占用任何赛车，但是当然比赛用时也会被认为是无 穷。 任何时候，一旦存在若干个（至少 3 个）晶片 A,B,C,…,X 满足：A 与 B 建 立了连接，B 与 C 建立了连接，……，X 与 A 建立了连接（即形成了循环连接 的情况） ，那么处理系统就会崩溃。这是非常可怕的，我们宁可让比赛用时变为 无穷也不能让系统崩溃。 现在给出队员和赛车的信息，请输出最优情况下的成绩（即第𝑘小的比赛时 间的最小值）。 为了增大难度，𝑘并不是给出的，而是你需要对于1 ≤ 𝑘 ≤ 𝑛的所 有的𝑘输出答案。
【输入文件】
第一行为两个整数𝑛 𝑚。 接下来𝑚行，每行描述了一个赛车，格式为空格隔开的一个整数和两个字符 串，分别是𝑎𝑖和它的两个终端对应的 GP 晶片名。
【输出文件】
𝑛行，每行一个整数，第𝑖行表示𝑖 = 𝑘时的答案。特别地，如果答案是无穷， 输出 INF。
【输入样例】
3 3
95 GP_1 GP_2
100 GP_1 gp@3
100 gp@3 GP_2
Solution
打的舒舒服服，是开始看这道题的时候，就感觉到了这个系列赛的典型特点，题目背景是什么鬼？？强行四驱车一波….吐槽完毕，还是比较裸的一道题，都已经说了无环，以我现在这个知识水平也就最小生成树了.还有什么hash 离散化的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
| #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <vector> #define ULL unsigned long long #define LL long long using namespace std; struct node{ ULL a,b; LL w; int gp1,gp2; friend bool operator < (node a,node b){ return a.w<b.w; } }car[100010]; char gp[2][100]; int fa[100010]; ULL c[200010]; int findf(int x){ if(fa[x]==x)return fa[x]; else return fa[x]=findf(fa[x]); } void mergef(int x,int y) { int tx=findf(x),ty=findf(y); fa[tx]=ty; } int main() { freopen("letsandgo.in","r",stdin); freopen("letsandgo.out","w",stdout); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%lld",&car[i].w); scanf("%s%s",gp[0],gp[1]); ULL gp1=0,gp2=0; int len=strlen(gp[0]); for(int j=0;j<len;j++)gp1=gp1*255+gp[0][j]; len=strlen(gp[1]); for(int j=0;j<len;j++)gp2=gp2*255+gp[1][j]; c[++c[0]]=gp1; c[++c[0]]=gp2; car[i].a=gp1,car[i].b=gp2; } sort(car+1,car+1+m); sort(c+1,c+c[0]+1); int tot=0; for(int i=1;i<=c[0];i++)if(c[i]!=c[i-1])c[++tot]=c[i]; for(int i=1;i<=m;i++) { ULL x=car[i].a,y=car[i].b; int g1=lower_bound(c+1,c+1+tot,x)-c; int g2=lower_bound(c+1,c+1+tot,y)-c; car[i].gp1=g1,car[i].gp2=g2; } for(int i=1;i<=tot;i++)fa[i]=i; for(int i=1;i<=m&&n>0;i++) { if(findf(car[i].gp1)!=findf(car[i].gp2)) { mergef(car[i].gp1,car[i].gp2); printf("%lld\n",car[i].w); n--; } } while(n--) { printf("INF\n"); } return 0; } 3 3 95 GP_1 GP_2 100 GP_1 gp@3 100 gp@3 GP_2 10 10 100 a b 165 asd df 98 sdg gsfd 12 fsa er 948 stf th 126 sdf hg 16 srdy gd 546 fgh ty 46 dr jgh 945 ah ty */
|
